import java.util.ArrayList;
import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=912 lang=java
 *
 * [912] 排序数组
 *
 * https://leetcode-cn.com/problems/sort-an-array/description/
 *
 * algorithms
 * Medium (52.00%)
 * Likes:    35
 * Dislikes: 0
 * Total Accepted:    13.1K
 * Total Submissions: 25.1K
 * Testcase Example:  '[5,2,3,1]'
 *
 * 给定一个整数数组 nums，将该数组升序排列。
 *
 *
 *
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：[5,2,3,1]
 * 输出：[1,2,3,5]
 *
 *
 * 示例 2：
 *
 *
 * 输入：[5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= A.length <= 10000
 * -50000 <= A[i] <= 50000
 *
 *
 */

// @lc code=start
class Solution {
    public List<Integer> sortArray(int[] nums) {
        // quickSort(nums, 0, nums.length-1);
        //heapSort(nums);
        Arrays.sort(nums);
        List<Integer> list  = new ArrayList<>();
        for(int n : nums) {
            list.add(n);
        }
        return list;
    }

    void quickSort(int[] nums, int left, int right) {
        if(left >= right)
            return;
        int l = left, r = right;
        while(l < r) {
            while (l < r && nums[l] <= nums[r]) {
                r--;
            }
            int n = nums[l];
            nums[l] = nums[r];
            nums[r] = n;
            while (l < r && nums[l] <= nums[r]) {
                l++;
            }
            n = nums[l];
            nums[l] = nums[r];
            nums[r] = n;
        }
        quickSort(nums, left, l-1);
        quickSort(nums, r+1, right);
    }

    void heapSort(int[] nums) {
        buildHeap(nums);
        for(int i=nums.length-1; i > -1; i--) {
            int tmp = nums[i];
            nums[i] = nums[0];
            nums[0] = tmp;
            checkHeap(nums, i);
        }
    }

    void buildHeap(int[] nums) {
        for(int i=0; i < nums.length; i++) {
            int cur = i, par = (cur+1)/2 - 1;
            while(par>-1 && nums[par] < nums[cur]) {
                int tmp = nums[par];
                nums[par] = nums[cur];
                nums[cur] = tmp;
                cur = par; par = (cur+1)/2 - 1;
            }
        }
    }
    // [-4,0,7,4,9,-5,-1,0,-7,-1]
    void checkHeap(int[] nums, int r) {
        int cur = 0, left = (cur+1) << 1 - 1, right = (cur+1) << 1;
        while(  left < r && nums[cur] < nums[left] ||
             right < r && nums[cur] < nums[right]) {
            int index = left;
            if(right < r && nums[left] < nums[right]) {
                index = right;
            }
            int tmp = nums[index];
            nums[index] = nums[cur];
            nums[cur] = tmp;
            cur = index; left = ((cur+1) << 1) - 1; right = (cur+1) << 1;
        }
    }
}
// @lc code=end

